A typical echo cancellation application is shown in FIG. 1. The transmitted speech or signal is fed back to the received end becoming echo to the incoming speech. The echo reflection is caused by either impedance mismatch as in a network application or room reflection in an acoustical application. The echo will distort the incoming signal and speech.
In telephony application, the echo is very annoying to the people on the phone. An adaptive algorithm is always applied to monitor the echo path and its variation so that it can be replicated by a linear filter and then subtracted from the incoming signal. For the telephony application, the speech signal is non-stationary and has a huge dynamic range.
One adaptive algorithm is known as the Affine Projection Algorithm(APA), K. Ozeki and T. Umeda, “An Adaptive Filtering Algorithm Using an Orthogonal Projection to an Affine Subspace and Its Properties”, Electronics and Communications in Japan, Vol.67-A, No.5, 1984. This is a generalization of the well known normalized least mean square (NLMS) adaptive algorithm. It has a much faster convergence rate than the LMS algorithm and its fast implementation has similar computational complexity as the LMS algorithm.
The LMS algorithm can be seen as a special case of APA where the projection order is 1. With the increase of projection order, the APA starts showing a dramatic increase of convergence speed. When the projection order is over 5, the increase of converge speed shows only a slight improvement. When the projection order increases to the order of filter size, the APA becomes the Recursive Least Square Algorithm (RLS).The APA is a very attractive algorithm which has the same complexity as LMS but is able to achieve RLS performance. In general, the convergence speed doubles with a doubling of projection order.
The original APA needs more data memory than the NLMS algorithm and its complexity is equivalent to the N times of NLMS algorithm (here N is the order of projection. However, because of information and data reuse, many computation procedures can be saved and reused. This is the fundamental idea of the Fast Affine Projection (FAP) algorithm. However, the APA involves an Nth-order matrix inverse. There are different methods available for the matrix inverse which differentiates various algorithms with different performance, complexity and stability. The most important issue is that no matter what methods are, the problem of non-stability with large matrix inverse remains, especially with its fast operation and finite precision implementation. Singular value decomposition, J. Cioffi and T. Kailath, “Windowed Fast Transversal Filters Adaptive Algorithms with Normalization”, IEEE Trans. on ASSP, Vol.ASSP-33, No.3, June 1985, is the most stable implementation of matrix inverse and its only problem is its computational complexity.
When dealing with a large matrix, there is always the singularity problem. With finite precision and fixed point implementation, the inverse of singular matrix will make the whole system very unstable because the smallest eigenvalue dominates the whole inverse matrix. In either APA or FAP algorithms, an identity matrix multiplied by a small constant is added to the inverse matrix so that the matrix will never become a singularity. However, this constant will cause performance degradation for the adaptive system. If this constant is too big, the performance degradation is severe and if this constant is too small, system stability cannot be maintained unless more data precision is employed in the echo cancellation.